package recusive;

import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

/**
 * @author luo
 * @description
 * @since 2022/7/21 20:53
 */
public class ThreeSumClosest {

    private int xIndex;
    private int yIndex;
    private int zIndex;
    /**
     * 当前最接近的和
     */
    private int currentClosestSum = Integer.MAX_VALUE;
    private int[] nums;
    private int[] sortTemp;
    private int target;

    @BeforeEach
    public void init() {
        nums = new Random(47).ints(10_000_000).toArray();
//        nums = new int[]{10, 9,7, 6, 5, 8, 4, 3, 2, 1};
        this.sortTemp = new int[nums.length];
    }

    @DisplayName("最接近的三数之和")
    @Test
    public void threeSumClosest() {
        int i = threeSumClosest(new int[]{-1,2,1,-4}, 1);
        System.out.println("最接近的数的和是：" + i);
        System.out.printf("他们分别是索引位置上的：arr[%d] = %d,arr[%d] = %d,arr[%d]=%d\n", xIndex, nums[xIndex], yIndex, nums[yIndex], zIndex, nums[zIndex]);
    }

    public int threeSumClosest(int[] numbers, int target) {
        this.nums = numbers;
        sort(0, this.nums.length - 1);
        this.target = target;
        for (int i = 1; i < nums.length; i++) {
            find(i);
        }

        return currentClosestSum;
    }


    private void sort(int left, int right) {
        if (left == right) {
            sortTemp[left] = nums[left];
            return;
        }
        int middle = (left + right) / 2;
//        将传入的范围分成两半，分别递归
        sort(left, middle);
        sort(middle + 1, right);
//        递归完成，开始合并
        for (int i = left, j = middle + 1, leftValue = 0, rightValue = 0, currentIndex = left; currentIndex <= right; currentIndex++) {
            leftValue = sortTemp[i];
            rightValue = sortTemp[j];
            if (leftValue <= rightValue) {
                nums[currentIndex] = leftValue;
                if (i == middle) {
                    for (int k = currentIndex + 1; k <= right; k++) {

                        nums[k] = sortTemp[j];
                        j++;
                    }
                    break;
                }
                i++;
            } else {
                nums[currentIndex] = rightValue;
                if (j == right) {
                    for (int k = currentIndex + 1; k <= right; k++) {
                        nums[k] = sortTemp[i];
                        i++;
                    }
                    break;
                }
                j++;
            }
        }
        for (int i = left; i <= right; i++) {
            sortTemp[i] = nums[i];
        }
    }

    private void find(int currentIndex) {
        int firstValue = 0;

        int need = 0;
        int actualNeedValue = 0;
        int currentValue = nums[currentIndex];
        for (int firstIndex = 0; firstIndex < currentIndex; firstIndex++) {
            firstValue = nums[firstIndex];

            for (int thirdIndex = currentIndex + 1; thirdIndex < nums.length; thirdIndex++) {


                actualNeedValue = nums[thirdIndex];
                int sum = firstValue + currentValue + actualNeedValue;
                if (Math.abs(Math.abs(target) - Math.abs(sum)) < Math.abs(Math.abs(target) -Math.abs(currentClosestSum) )) {
                    currentClosestSum = sum;
                    xIndex = firstIndex;
                    yIndex = currentIndex;
                    zIndex = thirdIndex;
                }
            }

        }


    }

    /**
     * 找到最接近的值
     *
     * @param left
     * @param right
     * @param need
     * @return
     */
    private int findClosestVal(int left, int right, int need) {
        if (left >= right) {
            return left;
        }
        int middle = (left + right) / 2;
        int middleValue = nums[middle];
        if (need > middleValue) {
            return findClosestVal(middle + 1, right, need);
        } else if (need < middleValue) {
            return findClosestVal(left, middle - 1, need);
        } else {
            return middleValue;
        }
    }


    @DisplayName("jdk自带的排序")
    @Test
    public void jdkSort() {

        ArrayList<Integer> integers = new ArrayList<>(nums.length);
        for (int num : nums) {
            integers.add(num);
        }
        long l = System.currentTimeMillis();
        integers.sort(Integer::compare);
        System.out.println("jdk排序完成：" + (System.currentTimeMillis() - l) + "ms");
        showResult();

    }

    @DisplayName("测试分治排序")
    @Test
    public void sortTest() {

        long l = System.currentTimeMillis();

        sort(0, nums.length - 1);

        System.out.println("我的归并排序完成：" + (System.currentTimeMillis() - l) + "ms");

        int lastNum = Integer.MIN_VALUE;
        showResult();

        for (int i = 0; i < nums.length; i++) {
            int val = nums[i];
            if (val < lastNum) {
                throw new IllegalStateException("排序失败，位于index = " + i + "的" + val + "小于上一个值" + lastNum);
            }
            lastNum = val;
        }
//        -1836110746
//        -1791886538

    }

    private void showResult() {
        if (nums.length < 2000) {

            System.out.println(Arrays.toString(nums));
        }
    }
}
